为什么会堆栈溢出问题? | 您所在的位置:网站首页 › 堆栈溢出一般是由什么原因导致的 weblogic › 为什么会堆栈溢出问题? |
在一个算法中,如果递归函数调用过多次数,那么就会导致堆栈溢出。 原因就是,操作系统会自动给每个进程分配一个最大栈空间2M,如果超过了这个上限,就会导致递归函数执行终止,所以就会报错。递归就像你一直在往一个空间里放东西,也就是一直在入栈,调用一次会把内存地址进行一次入栈,直到调用结束,才会将地址出栈。想一想,是不是如果调用次数过多,入栈的内存地址大于2M,就会引起程序报错呢? 同样的,如果你创建一个数组过大,会引起堆溢出,操作系统给每个进程分配的最大堆空间是4G,如果过大会导致堆溢出。 ※(调用一个方法,在这个方法执行前都会将之前的内存地址(也就是调用点)入栈,等被调用的方法执行完将地址出栈,程序根据这个数据返回调用点) 解决递归函数堆栈溢出的方法就是尾递归: 尾递归就是在函数返回return时调用函数本身,而不使用其他表达式。这样执行的时候尾递归函数只会占用一个栈帧,就不会引起栈溢出。 下面是2个例子: def fact(n): if n==1: return 1 return n * fact(n - 1) def fact_iter(num, product): if num == 1: return product return fact_iter(num - 1, num * product)第一个就是递归函数;第二个就是优化后的尾递归。
很经典的递归算法例子-----【汉诺塔】: 汉诺塔是由三根杆子A,B,C组成的。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。问:如何移?最少要移动多少次?汉诺塔是根据一个传说形成的一个问题: 有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆: 每次只能移动一个圆盘; 大盘不能叠在小盘上面。 以下是,答案及思路: def move(n, a, b, c): if n == 1: print('move', a, '-->', c) else: move(n-1, a, c, b) //先将初始柱A的前n-1个盘子借助目的柱C移动到借用柱B上 move(1, a, b, c) //将A柱剩下的一个最大盘子移动到目标C柱上 move(n-1, b, a, c) //最后将B柱上的n-1个盘子移动到目标C柱上 move(4, 'A', 'B', 'C')
|
CopyRight 2018-2019 实验室设备网 版权所有 |